Prof. Dr. Michael Ralph Fellows

Profil

Derzeitige StellungProfessor W-3 und Äquivalente
FachgebietTheoretische Informatik,Softwaretechnik und Programmiersprachen
KeywordsFPT kernelization, Algorithm Design, Computational Biology, Computational Complexity, Data Reduction, Fixed-Parameter Algorithms

Aktuelle Kontaktadresse

LandNorwegen
OrtBergen
Universität/InstitutionUniversity of Bergen
Institut/AbteilungDepartment of Informatics

Gastgeber*innen während der Förderung

Prof. Dr. Rolf NiedermeierInstitut für Informatik, Friedrich-Schiller-Universität Jena, Jena
Prof. Dr. Matthias MnichTechnische Universität Hamburg (TUHH), Hamburg
Beginn der ersten Förderung01.08.2007

Programm(e)

2006Forschungspreis-Programm auf Gegenseitigkeit für Wissenschaftler*innen aus dem Ausland

Projektbeschreibung der*des Nominierenden

Professor Fellows is recognized for his foundational research in theoretical computer science that created the subject of parameterized complexity and algorithmics. This approach to the design of algorithms and the analysis of problem complexity has had significant impact in diverse application areas including databases, artificial intelligence and bioinformatics. In Germany, Professor Fellows will work on new systematic approaches to parameterized algorithm design for problems arising in various fields.

Publikationen (Auswahl)

2009Michael Ralph Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier: A Generalization of Nemhauser and Trotter's Local Optimization Theorem. In: STACS Proceedings 2009, 2009, 409-420
2009Hans L. Bodlaender, Michael R. Fellows, Dimitrios M. Thilikos: Derivation of algorithms for cutwidth and related graph layout parameters. In: Journal Computation System Science, 2009, 231-244
2009Michael Ralph Fellows, Danny Hermelin, Frances A. Rosamond, Stéphane Vialette: On the parameterized complexity of multiple-interval graph problems. In: Theoretical Computer Science, 2009, 53-61
2009Michael Dom, Michael R. Fellows, Frances A. Rosamond: Parameterized Complexity of Stabbing Rectangles and Squares in the Plane. In: Lecture Notes in Computer Science: Proc 3rd WALCOM Confe, 2009, 298-309
2008Michael Ralph Fellows, Danny Hermelin, Moritz Müller, Frances A. Rosamond: A Purely Democratic Characterization of W[1]. . In: IWPEC 2008, 2008, 103-114
2008Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier: Algorithms and Hardness Results for Some Graph Motif Problems. In: CPM 2008, 2008, 31-43
2008Michael R. Fellows, Henning Fernau: Facility Location Problems: A Parameterized View. In: AAIM 2008, 2008, 188-199
2008Michael Ralph Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides: Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. In: Algorithmica, 2008, 167-176
2008Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, Frances A. Rosamond: Fixed-Parameter Algorithms for Kemeny Scores . In: AAIM 2008, 2008, 60-71
2008Michael Ralph Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, Saket Saurabh: Graph Layout Problems Parameterized by Vertex Cover. In: ISAAC2008, 2008, 294-305
2008Michael Ralph Fellows, Daniel Meister, Frances A. Rosamond, R. Sritharan, Jan Arne Telle: Leaf Powers and Their Properties: Using the Trees. In: ISAAC2008, 2008, 402-413
2008Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On Problems without Polynomial Kernels . In: ICALP(1)2008, 2008, 563-574
2008Vida Dujmovic, Michael R. Fellows, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Sue Whitesides, David R. Wood: On the Parameterized Complexity of Layered Graph Drawing. In: Algorithmica, 2008, 267-292
2008Michael Ralph Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh: Parameterized Low-distortion Embeddings - Graph metrics into lines and trees . In: CoRR abs/0804.3028: (2008), 2008, 1-14
2008Rodney G. Downey, Michael R. Fellows, Catherine McCartin, Frances A. Rosamond: Parameterized approximation of dominating set problems. In: Information Processing Letters, 2008, 68-70
2008Michael Ralph Fellows, Rodney G. Downey, Michael A. Langston: The Computer Journal Special Issue on Parameterized Complexity: Foreword by the Guest Editors. In: The Computer Journal, 2008, 1-6
2007Michael Ralph Fellows, Fedor V. Fomin, Daniel Lokshtanov, Frances A. Rosamond, Saket Saurabh, Stefan Szeider, Carsten Thomassen: On the Complexity of Some Colorful Problems Parameterized by Treewidth. In: COCOA 2007, 2007, 366-377